{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Bomb Enemy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxKilledEnemies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #轰炸敌人"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为 <code>m x n</code> 的矩阵 <code>grid</code> ，其中每个单元格都放置有一个字符：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>'W'</code>&nbsp;表示一堵墙</li>\n",
    "\t<li><code>'E'</code>&nbsp;表示一个敌人</li>\n",
    "\t<li><code>'0'</code>（数字 0）表示一个空位</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回你使用 <strong>一颗炸弹</strong> 可以击杀的最大敌人数目。你只能把炸弹放在一个空位里。</p>\n",
    "\n",
    "<p>由于炸弹的威力不足以穿透墙体，炸弹只能击杀同一行和同一列没被墙体挡住的敌人。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/27/bomb1-grid.jpg\" style=\"width: 600px; height: 187px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[\"0\",\"E\",\"0\",\"0\"],[\"E\",\"0\",\"W\",\"E\"],[\"0\",\"E\",\"0\",\"0\"]]\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/27/bomb2-grid.jpg\" style=\"width: 500px; height: 194px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[\"W\",\"W\",\"W\"],[\"0\",\"0\",\"0\"],[\"E\",\"E\",\"E\"]]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 500</code></li>\n",
    "\t<li><code>grid[i][j]</code> 可以是 <code>'W'</code>、<code>'E'</code> 或 <code>'0'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [bomb-enemy](https://leetcode.cn/problems/bomb-enemy/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [bomb-enemy](https://leetcode.cn/problems/bomb-enemy/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"0\",\"E\",\"0\",\"0\"],[\"E\",\"0\",\"W\",\"E\"],[\"0\",\"E\",\"0\",\"0\"]]', '[[\"W\",\"W\",\"W\"],[\"0\",\"0\",\"0\"],[\"E\",\"E\",\"E\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        blastZone = [[0] * n for _ in range(m)]\n",
    "\n",
    "        # handle row\n",
    "        for i in range(m):\n",
    "            prefix = 0\n",
    "            postfix = 0\n",
    "            for j in range(n):\n",
    "                # prefix\n",
    "                if grid[i][j] == 'W':\n",
    "                    prefix = 0\n",
    "                elif grid[i][j] == 'E':\n",
    "                    prefix += 1\n",
    "                else:\n",
    "                    blastZone[i][j] += prefix\n",
    "\n",
    "                # postfix\n",
    "            for j in range(n-1, -1, -1):\n",
    "                # prefix\n",
    "                if grid[i][j] == 'W':\n",
    "                    postfix = 0\n",
    "                elif grid[i][j] == 'E':\n",
    "                    postfix += 1\n",
    "                else:\n",
    "                    blastZone[i][j] += postfix\n",
    "\n",
    "\n",
    "        # handle col\n",
    "        for j in range(n):\n",
    "            prefix = 0\n",
    "            postfix = 0\n",
    "\n",
    "            for i in range(m):\n",
    "                # prefix\n",
    "                if grid[i][j] == 'W':\n",
    "                    prefix = 0\n",
    "                elif grid[i][j] == 'E':\n",
    "                    prefix += 1\n",
    "                else:\n",
    "                    blastZone[i][j] += prefix\n",
    "\n",
    "                # postfix\n",
    "            for i in range(m-1, -1, -1):\n",
    "                # prefix\n",
    "                if grid[i][j] == 'W':\n",
    "                    postfix = 0\n",
    "                elif grid[i][j] == 'E':\n",
    "                    postfix += 1\n",
    "                else:\n",
    "                    blastZone[i][j] += postfix\n",
    "\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "\n",
    "                res = max(res, blastZone[i][j])\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        if not grid: return 0\n",
    "        res = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        row_matrix = [[0]*n for _ in range(m)]\n",
    "        col_matrix = [[0]*n for _ in range(m)]\n",
    "        # 行矩阵\n",
    "        i = 0\n",
    "        while i < m:\n",
    "            cnt, pre, j = 0, 0, 0\n",
    "            while j < n:\n",
    "                if grid[i][j] == \"W\":  # 墙\n",
    "                    row_matrix[i][pre: j] = [cnt]*(j-pre)\n",
    "                    cnt = 0\n",
    "                    pre = j\n",
    "                elif grid[i][j] == \"E\":  # enemy\n",
    "                    cnt += 1\n",
    "                j += 1\n",
    "            row_matrix[i][pre: j] = [cnt]*(j-pre)  # 最后\n",
    "            i += 1\n",
    "        # 列矩阵\n",
    "        j = 0\n",
    "        while j < n:\n",
    "            cnt, pre, i = 0, 0, 0\n",
    "            while i < m:\n",
    "                if grid[i][j] == \"W\":  # 墙\n",
    "                    for index in range(pre, i):\n",
    "                        col_matrix[index][j] = cnt\n",
    "                    cnt = 0\n",
    "                    pre = i\n",
    "                elif grid[i][j] == \"E\":  # enemy\n",
    "                    cnt += 1\n",
    "                i += 1\n",
    "            for index in range(pre, i):\n",
    "                col_matrix[index][j] = cnt # 最后\n",
    "            j += 1\n",
    "        # 最后对空位置遍历\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '0':\n",
    "                    res = max(res, row_matrix[i][j]+col_matrix[i][j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        if not grid:\n",
    "            return 0\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        max_kills = 0\n",
    "        row_hits = 0\n",
    "        col_hits = [0] * n\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j == 0 or grid[i][j - 1] == 'W':\n",
    "                    row_hits = 0\n",
    "                    for k in range(j, n):\n",
    "                        if grid[i][k] == 'W':\n",
    "                            break\n",
    "                        if grid[i][k] == 'E':\n",
    "                            row_hits += 1\n",
    "\n",
    "                if i == 0 or grid[i - 1][j] == 'W':\n",
    "                    col_hits[j] = 0\n",
    "                    for k in range(i, m):\n",
    "                        if grid[k][j] == 'W':\n",
    "                            break\n",
    "                        if grid[k][j] == 'E':\n",
    "                            col_hits[j] += 1\n",
    "\n",
    "                if grid[i][j] == '0':\n",
    "                    max_kills = max(max_kills, row_hits + col_hits[j])\n",
    "\n",
    "        return max_kills\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        if not grid: return 0\n",
    "        res = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        row_matrix = [[0]*n for _ in range(m)]\n",
    "        col_matrix = [[0]*n for _ in range(m)]\n",
    "        # 行矩阵\n",
    "        i = 0\n",
    "        while i < m:\n",
    "            cnt, pre, j = 0, 0, 0\n",
    "            while j < n:\n",
    "                if grid[i][j] == \"W\":  # 墙\n",
    "                    row_matrix[i][pre: j] = [cnt]*(j-pre)\n",
    "                    cnt = 0\n",
    "                    pre = j\n",
    "                elif grid[i][j] == \"E\":  # enemy\n",
    "                    cnt += 1\n",
    "                j += 1\n",
    "            row_matrix[i][pre: j] = [cnt]*(j-pre)  # 最后\n",
    "            i += 1\n",
    "        # 列矩阵\n",
    "        j = 0\n",
    "        while j < n:\n",
    "            cnt, pre, i = 0, 0, 0\n",
    "            while i < m:\n",
    "                if grid[i][j] == \"W\":  # 墙\n",
    "                    for index in range(pre, i):\n",
    "                        col_matrix[index][j] = cnt\n",
    "                    cnt = 0\n",
    "                    pre = i\n",
    "                elif grid[i][j] == \"E\":  # enemy\n",
    "                    cnt += 1\n",
    "                i += 1\n",
    "            for index in range(pre, i):\n",
    "                col_matrix[index][j] = cnt # 最后\n",
    "            j += 1\n",
    "        # 最后对空位置遍历\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '0':\n",
    "                    res = max(res, row_matrix[i][j]+col_matrix[i][j])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        blastZone = [[0] * n for _ in range(m)]\n",
    "\n",
    "        # handle row\n",
    "        for i, row in enumerate(grid):\n",
    "            prefix = 0\n",
    "            postfix = 0\n",
    "            for j in range(n):\n",
    "                # prefix\n",
    "                if row[j] == 'W':\n",
    "                    prefix = 0\n",
    "                elif row[j] == 'E':\n",
    "                    prefix += 1\n",
    "                else:\n",
    "                    blastZone[i][j] += prefix\n",
    "\n",
    "                # postfix\n",
    "                if row[-1-j] == 'W':\n",
    "                    postfix = 0\n",
    "                elif row[-1-j] == 'E':\n",
    "                    postfix += 1\n",
    "                else:\n",
    "                    blastZone[i][-1-j] += postfix\n",
    "\n",
    "        # handle col\n",
    "        for j, col in enumerate(zip(*grid)):\n",
    "            prefix = 0\n",
    "            postfix = 0\n",
    "\n",
    "            for i in range(m):\n",
    "                # prefix\n",
    "                if col[i] == 'W':\n",
    "                    prefix = 0\n",
    "                elif col[i] == 'E':\n",
    "                    prefix += 1\n",
    "                else:\n",
    "                    blastZone[i][j] += prefix\n",
    "\n",
    "                # postfix\n",
    "                if col[-1-i] == 'W':\n",
    "                    postfix = 0\n",
    "                elif col[-1-i] == 'E':\n",
    "                    postfix += 1\n",
    "                else:\n",
    "                    blastZone[-1-i][j] += postfix\n",
    "        \n",
    "        return max(max(x) for x in blastZone)\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        dp=[[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            count=0\n",
    "            for j in range (n):\n",
    "                if grid[i][j]=='W':\n",
    "                    count=0\n",
    "                elif grid[i][j]=='E':\n",
    "                    count+=1\n",
    "                dp[i][j]+=count\n",
    "            count=0\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if grid[i][j]=='W':\n",
    "                    count=0\n",
    "                elif grid[i][j]=='E':\n",
    "                    count+=1\n",
    "                dp[i][j]+=count\n",
    "        for j in range (n):\n",
    "            count=0\n",
    "            for i in range (m):\n",
    "                if grid[i][j]=='W':\n",
    "                    count=0\n",
    "                elif grid[i][j]=='E':\n",
    "                    count+=1\n",
    "                dp[i][j]+=count\n",
    "            count=0\n",
    "            for i in range(m-1,-1,-1):\n",
    "                if grid[i][j]=='W':\n",
    "                    count=0\n",
    "                elif grid[i][j]=='E':\n",
    "                    count+=1\n",
    "                dp[i][j]+=count\n",
    "        b=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]=='0':\n",
    "                    b=max(dp[i][j],b)\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        ans=[[0]*n for _ in range(m)]\n",
    "        #方向DP\n",
    "        #一个方向\n",
    "        #dp[i]表示当前位置这一行向左延伸击杀的最大敌人数目。\n",
    "        #向右,向上,向下\n",
    "        for i in range(m):\n",
    "            #先正向\n",
    "            pre=0\n",
    "            for j in range(1,n):\n",
    "                if grid[i][j-1]==\"W\":\n",
    "                    pre=0\n",
    "                elif grid[i][j-1]==\"E\":\n",
    "                    pre+=1\n",
    "                ans[i][j]+=pre\n",
    "            pre=0\n",
    "            #再逆向\n",
    "            for j in range(n-2,-1,-1):\n",
    "                if grid[i][j+1]==\"W\":\n",
    "                    pre=0\n",
    "                elif grid[i][j+1]==\"E\":\n",
    "                    pre+=1\n",
    "                ans[i][j]+=pre\n",
    "        for j in range(n):\n",
    "            pre=0\n",
    "            for i in range(1,m):\n",
    "                if grid[i-1][j]==\"W\":\n",
    "                    pre=0\n",
    "                elif grid[i-1][j]==\"E\":\n",
    "                    pre+=1\n",
    "                ans[i][j]+=pre\n",
    "            pre=0\n",
    "            for i in range(m-2,-1,-1):\n",
    "                if grid[i+1][j]==\"W\":\n",
    "                    pre=0\n",
    "                elif grid[i+1][j]==\"E\":\n",
    "                    pre+=1\n",
    "                ans[i][j]+=pre\n",
    "        res=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==\"0\":\n",
    "                    res=max(res,ans[i][j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        Row = len(grid)\n",
    "        if Row == 0:\n",
    "            return 0\n",
    "        Col = len(grid[0])\n",
    "        ##################### 思路： 从4个方向，向中心聚拢\n",
    "        dp = [[0 for _ in range(Col)] for _ in range(Row)]\n",
    "\n",
    "        ######## 先每行\n",
    "        for r in range(Row):\n",
    "            #### 从左至右\n",
    "            cnt = 0\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 'W':\n",
    "                    cnt = 0\n",
    "                elif grid[r][c] == 'E':\n",
    "                    cnt += 1\n",
    "                dp[r][c] += cnt\n",
    "            #### 从右至左\n",
    "            cnt = 0\n",
    "            for c in range(Col - 1, -1, -1):\n",
    "                if grid[r][c] == 'W':\n",
    "                    cnt = 0\n",
    "                elif grid[r][c] == 'E':\n",
    "                    cnt += 1\n",
    "                dp[r][c] += cnt\n",
    "        ######## 再每列\n",
    "        for c in range(Col):\n",
    "            #### 从上至下\n",
    "            cnt = 0\n",
    "            for r in range(Row):\n",
    "                if grid[r][c] == 'W':\n",
    "                    cnt = 0\n",
    "                elif grid[r][c] == 'E':\n",
    "                    cnt += 1\n",
    "                dp[r][c] += cnt\n",
    "            #### 从下往上\n",
    "            cnt = 0\n",
    "            for r in range(Row - 1, -1, -1):\n",
    "                if grid[r][c] == 'W':\n",
    "                    cnt = 0\n",
    "                elif grid[r][c] == 'E':\n",
    "                    cnt += 1\n",
    "                dp[r][c] += cnt\n",
    "        res = 0\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == '0':   #只有0的地方，才能放炸弹\n",
    "                    res = max(res, dp[r][c])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        if grid == None or len(grid) == 0:\n",
    "            return 0\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        cols = [0] * (n)\n",
    "        res = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            rows = 0\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '0':\n",
    "                    total = rows + cols[j]\n",
    "                    for k in range(j+1, n):\n",
    "                        if grid[i][k] == 'W':\n",
    "                            break\n",
    "                        if grid[i][k] == 'E':\n",
    "                            total +=1\n",
    "                    \n",
    "                    for k in range(i+1, m):\n",
    "                        if grid[k][j] == 'W':\n",
    "                            break\n",
    "                        if grid[k][j] == 'E':\n",
    "                            total +=1\n",
    "                    res = max(res, total)\n",
    "                elif grid[i][j] == 'W':\n",
    "                    rows = 0\n",
    "                    cols[j] = 0\n",
    "                else:\n",
    "                    rows +=1\n",
    "                    cols[j] +=1\n",
    "        return res\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        Row = len(grid)\n",
    "        if Row == 0:\n",
    "            return 0\n",
    "        Col = len(grid[0])\n",
    "        ##################### 思路： 从4个方向，向中心聚拢\n",
    "        dp = [[0 for _ in range(Col)] for _ in range(Row)]\n",
    "\n",
    "        ######## 先每行\n",
    "        for r in range(Row):\n",
    "            #### 从左至右\n",
    "            cnt = 0\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 'W':\n",
    "                    cnt = 0\n",
    "                elif grid[r][c] == 'E':\n",
    "                    cnt += 1\n",
    "                dp[r][c] += cnt\n",
    "            #### 从右至左\n",
    "            cnt = 0\n",
    "            for c in range(Col - 1, -1, -1):\n",
    "                if grid[r][c] == 'W':\n",
    "                    cnt = 0\n",
    "                elif grid[r][c] == 'E':\n",
    "                    cnt += 1\n",
    "                dp[r][c] += cnt\n",
    "        ######## 再每列\n",
    "        for c in range(Col):\n",
    "            #### 从上至下\n",
    "            cnt = 0\n",
    "            for r in range(Row):\n",
    "                if grid[r][c] == 'W':\n",
    "                    cnt = 0\n",
    "                elif grid[r][c] == 'E':\n",
    "                    cnt += 1\n",
    "                dp[r][c] += cnt\n",
    "            #### 从下往上\n",
    "            cnt = 0\n",
    "            for r in range(Row - 1, -1, -1):\n",
    "                if grid[r][c] == 'W':\n",
    "                    cnt = 0\n",
    "                elif grid[r][c] == 'E':\n",
    "                    cnt += 1\n",
    "                dp[r][c] += cnt\n",
    "        res = 0\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == '0':   #只有0的地方，才能放炸弹\n",
    "                    res = max(res, dp[r][c])\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f1 = [ [0] * n for _ in range(m) ]\n",
    "        f2 = [ [0] * n for _ in range(m) ]\n",
    "        for i in range(m):\n",
    "            t1 = 0\n",
    "            ep = []\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"E\":\n",
    "                    t1 += 1\n",
    "                elif grid[i][j] == \"0\":\n",
    "                    ep.append((i, j))\n",
    "                elif grid[i][j] == \"W\":\n",
    "                    for x, y in ep:\n",
    "                        f1[x][y] = t1\n",
    "                    t1 = 0\n",
    "                    ep = []\n",
    "            for x, y in ep:\n",
    "                f1[x][y] = t1\n",
    "        \n",
    "        for j in range(n):\n",
    "            t2 = 0\n",
    "            ep = []\n",
    "            for i in range(m):\n",
    "                if grid[i][j] == \"E\":\n",
    "                    t2 += 1\n",
    "                elif grid[i][j] == \"0\":\n",
    "                    ep.append((i, j))\n",
    "                elif grid[i][j] == \"W\":\n",
    "                    for x, y in ep:\n",
    "                        f2[x][y] = t2\n",
    "                    t2 = 0\n",
    "                    ep = []\n",
    "            for x, y in ep:\n",
    "                f2[x][y] = t2\n",
    "        #print(f1, f2)\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = max(ans, f1[i][j] + f2[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        ans=0\n",
    "        row=[[0]*n for _ in range(m)]\n",
    "        col=[[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j>0 and grid[i][j-1]!='W':\n",
    "                    row[i][j]=row[i][j-1]\n",
    "                if (j==0 and grid[i][j]!='W') or grid[i][j-1]=='W':\n",
    "                    k=j\n",
    "                    temp=0\n",
    "                    while k<n and grid[i][k]!='W':\n",
    "                        if grid[i][k]=='E':\n",
    "                            temp+=1\n",
    "                        k+=1\n",
    "                    row[i][j]=temp\n",
    "        for j in range(n):\n",
    "            for i in range(m):\n",
    "                if i>0 and grid[i-1][j]!='W':\n",
    "                    col[i][j]=col[i-1][j]\n",
    "                if (i==0 and grid[i][j]!='W') or grid[i-1][j]=='W':\n",
    "                    k=i\n",
    "                    temp=0\n",
    "                    while k<m and grid[k][j]!='W':\n",
    "                        if grid[k][j]=='E':\n",
    "                            temp+=1\n",
    "                        k+=1\n",
    "                    col[i][j]=temp\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]=='0':\n",
    "                    ans=max(ans,row[i][j]+col[i][j])\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "\n",
    "        Row = len(grid)\n",
    "\n",
    "        if Row == 0:\n",
    "\n",
    "            return 0\n",
    "\n",
    "        Col = len(grid[0])\n",
    "\n",
    "        ##################### 思路： 从4个方向，向中心聚拢\n",
    "\n",
    "        dp = [[0 for _ in range(Col)] for _ in range(Row)]\n",
    "\n",
    "\n",
    "\n",
    "        ######## 先每行\n",
    "\n",
    "        for r in range(Row):\n",
    "\n",
    "            #### 从左至右\n",
    "\n",
    "            cnt = 0\n",
    "\n",
    "            for c in range(Col):\n",
    "\n",
    "                if grid[r][c] == 'W':\n",
    "\n",
    "                    cnt = 0\n",
    "\n",
    "                elif grid[r][c] == 'E':\n",
    "\n",
    "                    cnt += 1\n",
    "\n",
    "                dp[r][c] += cnt\n",
    "\n",
    "            #### 从右至左\n",
    "\n",
    "            cnt = 0\n",
    "\n",
    "            for c in range(Col - 1, -1, -1):\n",
    "\n",
    "                if grid[r][c] == 'W':\n",
    "\n",
    "                    cnt = 0\n",
    "\n",
    "                elif grid[r][c] == 'E':\n",
    "\n",
    "                    cnt += 1\n",
    "\n",
    "                dp[r][c] += cnt\n",
    "\n",
    "        ######## 再每列\n",
    "\n",
    "        for c in range(Col):\n",
    "\n",
    "            #### 从上至下\n",
    "\n",
    "            cnt = 0\n",
    "\n",
    "            for r in range(Row):\n",
    "\n",
    "                if grid[r][c] == 'W':\n",
    "\n",
    "                    cnt = 0\n",
    "\n",
    "                elif grid[r][c] == 'E':\n",
    "\n",
    "                    cnt += 1\n",
    "\n",
    "                dp[r][c] += cnt\n",
    "\n",
    "            #### 从下往上\n",
    "\n",
    "            cnt = 0\n",
    "\n",
    "            for r in range(Row - 1, -1, -1):\n",
    "\n",
    "                if grid[r][c] == 'W':\n",
    "\n",
    "                    cnt = 0\n",
    "\n",
    "                elif grid[r][c] == 'E':\n",
    "\n",
    "                    cnt += 1\n",
    "\n",
    "                dp[r][c] += cnt\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for r in range(Row):\n",
    "\n",
    "            for c in range(Col):\n",
    "\n",
    "                if grid[r][c] == '0':   #只有0的地方，才能放炸弹\n",
    "\n",
    "                    res = max(res, dp[r][c])\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        if m==0:\n",
    "            return 0\n",
    "        n = len(grid[0])\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            cnt = 0\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"W\":\n",
    "                    cnt=0\n",
    "                elif grid[i][j]==\"E\":\n",
    "                    cnt+=1\n",
    "                dp[i][j] += cnt\n",
    "            cnt=0\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j]==\"W\":\n",
    "                    cnt=0\n",
    "                elif grid[i][j]==\"E\":\n",
    "                    cnt+=1\n",
    "                dp[i][j]+=cnt\n",
    "        \n",
    "        for j in range(n):\n",
    "            cnt = 0\n",
    "            for i in range(m):\n",
    "                if grid[i][j]==\"W\":\n",
    "                    cnt = 0\n",
    "                elif grid[i][j]==\"E\":\n",
    "                    cnt +=1\n",
    "                dp[i][j]+= cnt\n",
    "            cnt = 0\n",
    "            for i in range(m-1,-1,-1):\n",
    "                if grid[i][j] ==\"W\":\n",
    "                    cnt = 0\n",
    "                elif grid[i][j]==\"E\":\n",
    "                    cnt +=1\n",
    "                dp[i][j] +=cnt\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==\"0\":\n",
    "                    res = max(res, dp[i][j])\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        Row = len(grid)\n",
    "        if Row == 0:\n",
    "            return 0\n",
    "        Col = len(grid[0])\n",
    "        ##################### 思路： 从4个方向，向中心聚拢\n",
    "        dp = [[0 for _ in range(Col)] for _ in range(Row)]\n",
    "\n",
    "        ######## 先每行\n",
    "        for r in range(Row):\n",
    "            #### 从左至右\n",
    "            cnt = 0\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 'W':\n",
    "                    cnt = 0\n",
    "                elif grid[r][c] == 'E':\n",
    "                    cnt += 1\n",
    "                dp[r][c] += cnt\n",
    "            #### 从右至左\n",
    "            cnt = 0\n",
    "            for c in range(Col - 1, -1, -1):\n",
    "                if grid[r][c] == 'W':\n",
    "                    cnt = 0\n",
    "                elif grid[r][c] == 'E':\n",
    "                    cnt += 1\n",
    "                dp[r][c] += cnt\n",
    "        ######## 再每列\n",
    "        for c in range(Col):\n",
    "            #### 从上至下\n",
    "            cnt = 0\n",
    "            for r in range(Row):\n",
    "                if grid[r][c] == 'W':\n",
    "                    cnt = 0\n",
    "                elif grid[r][c] == 'E':\n",
    "                    cnt += 1\n",
    "                dp[r][c] += cnt\n",
    "            #### 从下往上\n",
    "            cnt = 0\n",
    "            for r in range(Row - 1, -1, -1):\n",
    "                if grid[r][c] == 'W':\n",
    "                    cnt = 0\n",
    "                elif grid[r][c] == 'E':\n",
    "                    cnt += 1\n",
    "                dp[r][c] += cnt\n",
    "        res = 0\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == '0':   #只有0的地方，才能放炸弹\n",
    "                    res = max(res, dp[r][c])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # boom[i][j] 表示元素[i,j] 上下左右四个方向上，敌人的总数量\n",
    "        boom = [[0] * n for _ in range(m)]\n",
    "        pre, ans = 0, 0\n",
    "        for i in range(m):\n",
    "            pre = 0\n",
    "            # 从左往右开始遍历\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 'W':\n",
    "                    pre = 0\n",
    "                elif grid[i][j] == 'E':\n",
    "                    pre += 1\n",
    "                boom[i][j] = pre\n",
    "            pre = 0\n",
    "            # 从右往左开始遍历\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if grid[i][j] == 'W':\n",
    "                    pre = 0\n",
    "                elif grid[i][j] == 'E':\n",
    "                    pre += 1\n",
    "                boom[i][j] += pre\n",
    "        for j in range(n):\n",
    "            pre = 0\n",
    "            # 从上往下开始遍历\n",
    "            for i in range(m):\n",
    "                if grid[i][j] == 'W':\n",
    "                    pre = 0\n",
    "                elif grid[i][j] == 'E':\n",
    "                    pre += 1\n",
    "                boom[i][j] += pre\n",
    "            pre = 0\n",
    "            # 从下往上开始遍历\n",
    "            for i in range(m - 1, -1, -1):\n",
    "                if grid[i][j] == 'W':\n",
    "                    pre = 0\n",
    "                elif grid[i][j] == 'E':\n",
    "                    pre += 1\n",
    "                boom[i][j] += pre\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '0':\n",
    "                    ans = max(ans, boom[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        if not m :\n",
    "            return 0\n",
    "        n = len(grid[0])\n",
    "        dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            cnt = [0,0]\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"W\":\n",
    "                    cnt[0] = 0\n",
    "                elif grid[i][j] == \"E\":\n",
    "                    cnt[0] += 1\n",
    "                else:\n",
    "                    dp[i][j] += cnt[0]\n",
    "                if grid[i][n - j - 1] == \"W\":\n",
    "                    cnt[1] = 0\n",
    "                elif grid[i][n - j - 1] == \"E\":\n",
    "                    cnt[1] += 1\n",
    "                else:\n",
    "                    dp[i][n - j - 1] += cnt[1]\n",
    "        for j in range(n):\n",
    "            cnt = [0,0]\n",
    "            for i in range(m):\n",
    "                if grid[i][j] == \"W\":\n",
    "                    cnt[0] = 0\n",
    "                elif grid[i][j] == \"E\":\n",
    "                    cnt[0] += 1\n",
    "                else:\n",
    "                    dp[i][j] += cnt[0]\n",
    "                if grid[m - i - 1][j] == \"W\":\n",
    "                    cnt[1] = 0\n",
    "                elif grid[m - i - 1][j] == \"E\":\n",
    "                    cnt[1] += 1\n",
    "                else:\n",
    "                    dp[m - i - 1][j] += cnt[1]\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            ans += dp[i]\n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        matrix = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j == 0:\n",
    "                    matrix[i][j] = 1 if grid[i][j] == \"E\" else 0\n",
    "                else:\n",
    "                    if grid[i][j] == \"E\":\n",
    "                        matrix[i][j] = matrix[i][j-1] + 1\n",
    "                    elif grid[i][j] == \"W\":\n",
    "                        matrix[i][j] = 0\n",
    "                    else:\n",
    "                        matrix[i][j] = matrix[i][j-1]\n",
    "        for i in range(m):\n",
    "            row_max = 0\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j] == \"W\":\n",
    "                    row_max = 0\n",
    "                else:\n",
    "                    row_max = max(row_max, matrix[i][j])\n",
    "                    matrix[i][j] = row_max\n",
    "\n",
    "        xmatrix = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        results = 0\n",
    "        for j in range(n):\n",
    "            for i in range(m):\n",
    "                if i == 0:\n",
    "                    xmatrix[i][j] = 1  if grid[i][j] == \"E\" else 0\n",
    "                elif grid[i][j] == \"E\":\n",
    "                    xmatrix[i][j] = xmatrix[i-1][j]+1\n",
    "                elif grid[i][j] == \"W\":\n",
    "                    xmatrix[i][j] = 0\n",
    "                else:\n",
    "                    xmatrix[i][j] = xmatrix[i-1][j]\n",
    "        for j in range(n):\n",
    "            col_max = 0\n",
    "            for i in range(m-1, -1, -1):\n",
    "                if grid[i][j] == \"W\":\n",
    "                    col_max = 0\n",
    "                else:\n",
    "                    col_max = max(col_max, xmatrix[i][j])\n",
    "                    xmatrix[i][j] = col_max\n",
    "                    if grid[i][j] == \"0\":\n",
    "                        results = max(results, col_max + matrix[i][j])\n",
    "        # print(matrix)\n",
    "        # print(xmatrix)\n",
    "        return results\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        row = len(grid)\n",
    "        if row == 0:\n",
    "            return 0\n",
    "        col = len(grid[0])\n",
    "        dp = [[0 for _ in range(col)] for _ in range(row)]\n",
    "\n",
    "        ### for each row\n",
    "        for r in range(row):\n",
    "            cnt = 0\n",
    "            for c in range(col):\n",
    "                if grid[r][c] == \"W\":\n",
    "                    cnt = 0\n",
    "                elif grid[r][c] == \"E\":\n",
    "                    cnt += 1\n",
    "                dp[r][c] += cnt\n",
    "\n",
    "            cnt = 0\n",
    "            for c in range(col-1, -1, -1):\n",
    "                if grid[r][c] == \"W\":\n",
    "                    cnt = 0\n",
    "                elif grid[r][c] == \"E\":\n",
    "                    cnt += 1\n",
    "                dp[r][c] += cnt\n",
    "        # for each col\n",
    "        for c in range(col):\n",
    "            cnt = 0\n",
    "            for r in range(row):\n",
    "                if grid[r][c] == \"W\":\n",
    "                    cnt = 0\n",
    "                elif grid[r][c] == \"E\":\n",
    "                    cnt += 1\n",
    "                dp[r][c] += cnt\n",
    "            cnt = 0\n",
    "            for r in range(row-1, -1, -1):\n",
    "                if grid[r][c] == \"W\":\n",
    "                    cnt = 0\n",
    "                elif grid[r][c] == \"E\":\n",
    "                    cnt += 1\n",
    "                dp[r][c] += cnt\n",
    "        res = 0\n",
    "        for r in range(row):\n",
    "            for c in range(col):\n",
    "                if grid[r][c] == \"0\":\n",
    "                    res = max(res, dp[r][c])\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        Row = len(grid)\n",
    "        if Row == 0:\n",
    "            return 0\n",
    "        Col = len(grid[0])\n",
    "        ##################### 思路： 从4个方向，向中心聚拢\n",
    "        dp = [[0 for _ in range(Col)] for _ in range(Row)]\n",
    "\n",
    "        ######## 先每行\n",
    "        for r in range(Row):\n",
    "            #### 从左至右\n",
    "            cnt = 0\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 'W':\n",
    "                    cnt = 0\n",
    "                elif grid[r][c] == 'E':\n",
    "                    cnt += 1\n",
    "                dp[r][c] += cnt\n",
    "            #### 从右至左\n",
    "            cnt = 0\n",
    "            for c in range(Col - 1, -1, -1):\n",
    "                if grid[r][c] == 'W':\n",
    "                    cnt = 0\n",
    "                elif grid[r][c] == 'E':\n",
    "                    cnt += 1\n",
    "                dp[r][c] += cnt\n",
    "        ######## 再每列\n",
    "        for c in range(Col):\n",
    "            #### 从上至下\n",
    "            cnt = 0\n",
    "            for r in range(Row):\n",
    "                if grid[r][c] == 'W':\n",
    "                    cnt = 0\n",
    "                elif grid[r][c] == 'E':\n",
    "                    cnt += 1\n",
    "                dp[r][c] += cnt\n",
    "            #### 从下往上\n",
    "            cnt = 0\n",
    "            for r in range(Row - 1, -1, -1):\n",
    "                if grid[r][c] == 'W':\n",
    "                    cnt = 0\n",
    "                elif grid[r][c] == 'E':\n",
    "                    cnt += 1\n",
    "                dp[r][c] += cnt\n",
    "        res = 0\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == '0':   #只有0的地方，才能放炸弹\n",
    "                    res = max(res, dp[r][c])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        # every = [[[[0]*2 for i in range(n)]] for _ in range(m)]\n",
    "        every = [[0]*n for _ in range(m)]\n",
    "        print(every)\n",
    "        for i in range(n):\n",
    "            number = 0\n",
    "            space= []\n",
    "            for j in range(m):\n",
    "                if grid[j][i] == 'E':\n",
    "                    number+=1\n",
    "                elif grid[j][i] == '0':\n",
    "                    space.append([j,i])\n",
    "                if grid[j][i] =='W' or j==m-1:\n",
    "                    while space:\n",
    "                        cur_location = space.pop()\n",
    "                        every[cur_location[0]][cur_location[1]] = number\n",
    "                    number = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            number = 0\n",
    "            space= []\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 'E':\n",
    "                    number+=1\n",
    "                elif grid[i][j] == '0':\n",
    "                    space.append([i,j])\n",
    "                if grid[i][j] =='W' or j==n-1:\n",
    "                    while space:\n",
    "                        cur_location = space.pop()\n",
    "                        every[cur_location[0]][cur_location[1]] = every[cur_location[0]][cur_location[1]]+number\n",
    "                    number = 0\n",
    "        print(every)\n",
    "        print(max(every[i] for i in range(m)))\n",
    "\n",
    "\n",
    "        return max(map(max, every))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        \n",
    "        s = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] != 'W':\n",
    "                    s[i][j] = (s[i][j - 1] if j else 0) + (grid[i][j] == 'E')\n",
    "            for j in range(m - 1, -1, -1):\n",
    "                if j != m - 1 and grid[i][j] != 'W' and grid[i][j + 1] != 'W': s[i][j] = s[i][j + 1]\n",
    "\n",
    "        s2 = [[0] * m for _ in range(n)]\n",
    "        for j in range(m):\n",
    "            for i in range(n):\n",
    "                if grid[i][j] != 'W':\n",
    "                    s2[i][j] = (s2[i - 1][j] if i else 0) + (grid[i][j] == 'E')\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                if i != n - 1 and grid[i][j] != 'W' and grid[i + 1][j] != 'W': s2[i][j] = s2[i + 1][j]\n",
    "\n",
    "        return max([s[i][j] + s2[i][j] for i in range(n) for j in range(m) if grid[i][j] == '0'], default = 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        up, down, left, right = [[0] * n for _ in range(m)], [[0] * n for _ in range(m)], [[0] * n for _ in range(m)], [[0] * n for _ in range(m)]\n",
    "        for j in range(n):\n",
    "            tmp = 0\n",
    "            for i in range(1, m):\n",
    "                if grid[i - 1][j] == 'W':\n",
    "                    tmp = 0\n",
    "                elif grid[i - 1][j] == 'E':\n",
    "                    tmp += 1\n",
    "                up[i][j] = tmp\n",
    "        for j in range(n):\n",
    "            tmp = 0\n",
    "            for i in range(m - 2, -1, -1):\n",
    "                if grid[i + 1][j] == 'W':\n",
    "                    tmp = 0\n",
    "                elif grid[i + 1][j] == 'E':\n",
    "                    tmp += 1\n",
    "                down[i][j] = tmp\n",
    "        for i in range(m):\n",
    "            tmp = 0\n",
    "            for j in range(1, n):\n",
    "                if grid[i][j - 1] == 'W':\n",
    "                    tmp = 0\n",
    "                elif grid[i][j - 1] == 'E':\n",
    "                    tmp += 1\n",
    "                left[i][j] = tmp\n",
    "        for i in range(m):\n",
    "            tmp = 0\n",
    "            for j in range(n - 2, -1, -1):\n",
    "                if grid[i][j + 1] == 'W':\n",
    "                    tmp = 0\n",
    "                elif grid[i][j + 1] == 'E':\n",
    "                    tmp += 1\n",
    "                right[i][j] = tmp\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '0':\n",
    "                    ans = max(ans, up[i][j] + down[i][j] + left[i][j] + right[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        mx=0\n",
    "        dp1=[[0]*n for _ in range(m)]\n",
    "        dp2=[[0]*n for _ in range(m)]\n",
    "        dp3=[[0]*n for _ in range(m)]\n",
    "        dp4=[[0]*n for _ in range(m)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==\"0\":\n",
    "                    if j!=0:\n",
    "                        dp1[i][j]=dp1[i][j-1]\n",
    "                elif grid[i][j]==\"E\":\n",
    "                    if j==0:\n",
    "                        dp1[i][j]=1\n",
    "                    else:\n",
    "                        dp1[i][j]=dp1[i][j-1]+1\n",
    "        for i in range(m):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if grid[i][j]==\"0\":\n",
    "                    if j!=n-1:\n",
    "                        dp2[i][j]=dp2[i][j+1]\n",
    "                elif grid[i][j]==\"E\":\n",
    "                    if j==n-1:\n",
    "                        dp2[i][j]=1\n",
    "                    else:\n",
    "                        dp2[i][j]=dp2[i][j+1]+1\n",
    "        for j in range(n):\n",
    "            for i in range(m):\n",
    "                if grid[i][j]==\"0\":\n",
    "                    if i!=0:\n",
    "                        dp3[i][j]=dp3[i-1][j]\n",
    "                elif grid[i][j]==\"E\":\n",
    "                    if i==0:\n",
    "                        dp3[i][j]=1\n",
    "                    else:\n",
    "                        dp3[i][j]=dp3[i-1][j]+1\n",
    "        for j in range(n):\n",
    "            for i in range(m-1,-1,-1):\n",
    "                if grid[i][j]==\"0\":\n",
    "                    if i!=m-1:\n",
    "                        dp4[i][j]=dp4[i+1][j]\n",
    "                elif grid[i][j]==\"E\":\n",
    "                    if i==m-1:\n",
    "                        dp4[i][j]=1\n",
    "                    else:\n",
    "                        dp4[i][j]=dp4[i+1][j]+1\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==\"0\":\n",
    "                    tmp=dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]\n",
    "                    mx=max(mx,tmp)\n",
    "       # print(dp2)\n",
    "        return mx\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        l=[[0]*n for _ in range(m)]\n",
    "        r=[[0]*n for _ in range(m)]\n",
    "        up=[[0]*n for _ in range(m)]\n",
    "        down=[[0]*n for _ in range(m)]\n",
    "        #方向DP\n",
    "        #一个方向\n",
    "        #dp[i]表示当前位置这一行向左延伸击杀的最大敌人数目。\n",
    "        #向右,向上,向下\n",
    "        for i in range(m):\n",
    "            #先正向\n",
    "            for j in range(1,n):\n",
    "                if grid[i][j-1]==\"W\":\n",
    "                    l[i][j]=0\n",
    "                elif grid[i][j-1]==\"E\":\n",
    "                    l[i][j]=l[i][j-1]+1\n",
    "                else:\n",
    "                    l[i][j]=l[i][j-1]\n",
    "            #再逆向\n",
    "            for j in range(n-2,-1,-1):\n",
    "                if grid[i][j+1]==\"W\":\n",
    "                    r[i][j]=0\n",
    "                elif grid[i][j+1]==\"E\":\n",
    "                    r[i][j]=r[i][j+1]+1\n",
    "                else:\n",
    "                    r[i][j]=r[i][j+1]\n",
    "        for j in range(n):\n",
    "            for i in range(1,m):\n",
    "                if grid[i-1][j]==\"W\":\n",
    "                    down[i][j]=0\n",
    "                elif grid[i-1][j]==\"E\":\n",
    "                    down[i][j]=down[i-1][j]+1\n",
    "                else:\n",
    "                    down[i][j]=down[i-1][j]\n",
    "            for i in range(m-2,-1,-1):\n",
    "                if grid[i+1][j]==\"W\":\n",
    "                    up[i][j]=0\n",
    "                elif grid[i+1][j]==\"E\":\n",
    "                    up[i][j]=up[i+1][j]+1\n",
    "                else:\n",
    "                    up[i][j]=up[i+1][j]\n",
    "        res=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==\"0\":\n",
    "                    res=max(res,l[i][j]+r[i][j]+up[i][j]+down[i][j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        # 左边\n",
    "        left = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            left[i][0] = int(grid[i][0] == 'E')\n",
    "            for j in range(1, n):\n",
    "                if grid[i][j] == 'W':\n",
    "                    left[i][j] = 0\n",
    "                else:\n",
    "                    left[i][j] = left[i][j-1] + int(grid[i][j] == 'E')\n",
    "\n",
    "        # 右边\n",
    "        right = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            right[i][n-1] = int(grid[i][n-1] == 'E')\n",
    "            for j in range(n-2, -1, -1):\n",
    "                if grid[i][j] == 'W':\n",
    "                    right[i][j] = 0\n",
    "                else:\n",
    "                    right[i][j] = right[i][j + 1] + int(grid[i][j] == 'E')\n",
    "        \n",
    "        # 上面\n",
    "        up = [[0] * n for _ in range(m)]\n",
    "        for j in range(n):\n",
    "            up[0][j] = int(grid[0][j] == 'E')\n",
    "            for i in range(1, m):\n",
    "                if grid[i][j] == 'W':\n",
    "                    up[i][j] = 0\n",
    "                else:\n",
    "                    up[i][j] = up[i-1][j] + int(grid[i][j] == 'E')\n",
    "        \n",
    "        # 下面\n",
    "        down = [[0] * n for _ in range(m)]\n",
    "        for j in range(n):\n",
    "            down[m-1][j] = int(grid[m-1][j] == 'E')\n",
    "            for i in range(m-2, -1, -1):\n",
    "                if grid[i][j] == 'W':\n",
    "                    down[i][j] = 0\n",
    "                else:\n",
    "                    down[i][j] = down[i+1][j] + int(grid[i][j] == 'E')\n",
    "        \n",
    "        # 枚举\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '0':\n",
    "                    cur = left[i][j] + right[i][j] + up[i][j] + down[i][j]\n",
    "                    if cur > ans:\n",
    "                        ans = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        l=[[0]*n for _ in range(m)]\n",
    "        r=[[0]*n for _ in range(m)]\n",
    "        up=[[0]*n for _ in range(m)]\n",
    "        down=[[0]*n for _ in range(m)]\n",
    "        #一个方向\n",
    "        #dp[i]表示当前位置这一行向左延伸击杀的最大敌人数目。\n",
    "        #向右,向上,向下\n",
    "        for i in range(m):\n",
    "            #先正向\n",
    "            for j in range(1,n):\n",
    "                if grid[i][j-1]==\"W\":\n",
    "                    l[i][j]=0\n",
    "                elif grid[i][j-1]==\"E\":\n",
    "                    l[i][j]=l[i][j-1]+1\n",
    "                else:\n",
    "                    l[i][j]=l[i][j-1]\n",
    "            #再逆向\n",
    "            for j in range(n-2,-1,-1):\n",
    "                if grid[i][j+1]==\"W\":\n",
    "                    r[i][j]=0\n",
    "                elif grid[i][j+1]==\"E\":\n",
    "                    r[i][j]=r[i][j+1]+1\n",
    "                else:\n",
    "                    r[i][j]=r[i][j+1]\n",
    "        for j in range(n):\n",
    "            for i in range(1,m):\n",
    "                if grid[i-1][j]==\"W\":\n",
    "                    down[i][j]=0\n",
    "                elif grid[i-1][j]==\"E\":\n",
    "                    down[i][j]=down[i-1][j]+1\n",
    "                else:\n",
    "                    down[i][j]=down[i-1][j]\n",
    "            for i in range(m-2,-1,-1):\n",
    "                if grid[i+1][j]==\"W\":\n",
    "                    up[i][j]=0\n",
    "                elif grid[i+1][j]==\"E\":\n",
    "                    up[i][j]=up[i+1][j]+1\n",
    "                else:\n",
    "                    up[i][j]=up[i+1][j]\n",
    "        res=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==\"0\":\n",
    "                    res=max(res,l[i][j]+r[i][j]+up[i][j]+down[i][j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        mx=0\n",
    "        dp1=[[0]*n for _ in range(m)]\n",
    "        dp2=[[0]*n for _ in range(m)]\n",
    "        dp3=[[0]*n for _ in range(m)]\n",
    "        dp4=[[0]*n for _ in range(m)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==\"0\":\n",
    "                    if j!=0:\n",
    "                        dp1[i][j]=dp1[i][j-1]\n",
    "                elif grid[i][j]==\"E\":\n",
    "                    if j==0:\n",
    "                        dp1[i][j]=1\n",
    "                    else:\n",
    "                        dp1[i][j]=dp1[i][j-1]+1\n",
    "        for i in range(m):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if grid[i][j]==\"0\":\n",
    "                    if j!=n-1:\n",
    "                        dp2[i][j]=dp2[i][j+1]\n",
    "                elif grid[i][j]==\"E\":\n",
    "                    if j==n-1:\n",
    "                        dp2[i][j]=1\n",
    "                    else:\n",
    "                        dp2[i][j]=dp2[i][j+1]+1\n",
    "        for j in range(n):\n",
    "            for i in range(m):\n",
    "                if grid[i][j]==\"0\":\n",
    "                    if i!=0:\n",
    "                        dp3[i][j]=dp3[i-1][j]\n",
    "                elif grid[i][j]==\"E\":\n",
    "                    if i==0:\n",
    "                        dp3[i][j]=1\n",
    "                    else:\n",
    "                        dp3[i][j]=dp3[i-1][j]+1\n",
    "        for j in range(n):\n",
    "            for i in range(m-1,-1,-1):\n",
    "                if grid[i][j]==\"0\":\n",
    "                    if i!=m-1:\n",
    "                        dp4[i][j]=dp4[i+1][j]\n",
    "                elif grid[i][j]==\"E\":\n",
    "                    if i==m-1:\n",
    "                        dp4[i][j]=1\n",
    "                    else:\n",
    "                        dp4[i][j]=dp4[i+1][j]+1\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==\"0\":\n",
    "                    tmp=dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]\n",
    "                    mx=max(mx,tmp)\n",
    "       # print(dp2)\n",
    "        return mx\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        mx=0\n",
    "        dp1=[[0]*n for _ in range(m)]\n",
    "        dp2=[[0]*n for _ in range(m)]\n",
    "        dp3=[[0]*n for _ in range(m)]\n",
    "        dp4=[[0]*n for _ in range(m)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==\"0\":\n",
    "                    if j!=0:\n",
    "                        dp1[i][j]=dp1[i][j-1]\n",
    "                elif grid[i][j]==\"E\":\n",
    "                    if j==0:\n",
    "                        dp1[i][j]=1\n",
    "                    else:\n",
    "                        dp1[i][j]=dp1[i][j-1]+1\n",
    "        for i in range(m):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if grid[i][j]==\"0\":\n",
    "                    if j!=n-1:\n",
    "                        dp2[i][j]=dp2[i][j+1]\n",
    "                elif grid[i][j]==\"E\":\n",
    "                    if j==n-1:\n",
    "                        dp2[i][j]=1\n",
    "                    else:\n",
    "                        dp2[i][j]=dp2[i][j+1]+1\n",
    "        for j in range(n):\n",
    "            for i in range(m):\n",
    "                if grid[i][j]==\"0\":\n",
    "                    if i!=0:\n",
    "                        dp3[i][j]=dp3[i-1][j]\n",
    "                elif grid[i][j]==\"E\":\n",
    "                    if i==0:\n",
    "                        dp3[i][j]=1\n",
    "                    else:\n",
    "                        dp3[i][j]=dp3[i-1][j]+1\n",
    "        for j in range(n):\n",
    "            for i in range(m-1,-1,-1):\n",
    "                if grid[i][j]==\"0\":\n",
    "                    if i!=m-1:\n",
    "                        dp4[i][j]=dp4[i+1][j]\n",
    "                elif grid[i][j]==\"E\":\n",
    "                    if i==m-1:\n",
    "                        dp4[i][j]=1\n",
    "                    else:\n",
    "                        dp4[i][j]=dp4[i+1][j]+1\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==\"0\":\n",
    "                    tmp=dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]\n",
    "                    mx=max(mx,tmp)\n",
    "       # print(dp2)\n",
    "        return mx\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        l=[[0]*n for _ in range(m)]\n",
    "        r=[[0]*n for _ in range(m)]\n",
    "        up=[[0]*n for _ in range(m)]\n",
    "        down=[[0]*n for _ in range(m)]\n",
    "        #方向DP\n",
    "        #一个方向\n",
    "        #dp[i]表示当前位置这一行向左延伸击杀的最大敌人数目。\n",
    "        #向右,向上,向下\n",
    "        for i in range(m):\n",
    "            #先正向\n",
    "            for j in range(1,n):\n",
    "                if grid[i][j-1]==\"W\":\n",
    "                    l[i][j]=0\n",
    "                elif grid[i][j-1]==\"E\":\n",
    "                    l[i][j]=l[i][j-1]+1\n",
    "                else:\n",
    "                    l[i][j]=l[i][j-1]\n",
    "            #再逆向\n",
    "            for j in range(n-2,-1,-1):\n",
    "                if grid[i][j+1]==\"W\":\n",
    "                    r[i][j]=0\n",
    "                elif grid[i][j+1]==\"E\":\n",
    "                    r[i][j]=r[i][j+1]+1\n",
    "                else:\n",
    "                    r[i][j]=r[i][j+1]\n",
    "        for j in range(n):\n",
    "            for i in range(1,m):\n",
    "                if grid[i-1][j]==\"W\":\n",
    "                    down[i][j]=0\n",
    "                elif grid[i-1][j]==\"E\":\n",
    "                    down[i][j]=down[i-1][j]+1\n",
    "                else:\n",
    "                    down[i][j]=down[i-1][j]\n",
    "            for i in range(m-2,-1,-1):\n",
    "                if grid[i+1][j]==\"W\":\n",
    "                    up[i][j]=0\n",
    "                elif grid[i+1][j]==\"E\":\n",
    "                    up[i][j]=up[i+1][j]+1\n",
    "                else:\n",
    "                    up[i][j]=up[i+1][j]\n",
    "        res=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==\"0\":\n",
    "                    res=max(res,l[i][j]+r[i][j]+up[i][j]+down[i][j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        up = [[0] * (n + 2) for _ in range(m + 2)]\n",
    "        down = [[0] * (n + 2) for _ in range(m + 2)]\n",
    "        left = [[0] * (n + 2) for _ in range(m + 2)]\n",
    "        right = [[0] * (n + 2) for _ in range(m + 2)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if grid[i - 1][j - 1] == 'E':\n",
    "                    left[i][j] = left[i][j - 1] + 1\n",
    "                    up[i][j] = up[i - 1][j] + 1\n",
    "                elif grid[i - 1][j - 1] == 'W':\n",
    "                    left[i][j] = 0\n",
    "                    up[i][j] = 0\n",
    "                else:\n",
    "                    left[i][j] = left[i][j - 1]\n",
    "                    up[i][j] = up[i - 1][j]\n",
    "        for i in range(m, 0, -1):\n",
    "            for j in range(n, 0, -1):\n",
    "                if grid[i - 1][j - 1] == 'E':\n",
    "                    right[i][j] = right[i][j + 1] + 1\n",
    "                    down[i][j] = down[i + 1][j] + 1\n",
    "                elif grid[i - 1][j - 1] == 'W':\n",
    "                    right[i][j] = 0\n",
    "                    down[i][j] = 0\n",
    "                else:\n",
    "                    right[i][j] = right[i][j + 1]\n",
    "                    down[i][j] = down[i + 1][j]\n",
    "        res = 0\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if grid[i - 1][j - 1] == '0':\n",
    "                    res = max(res, up[i - 1][j] + down[i + 1][j] + left[i][j - 1] + right[i][j + 1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        row1 = [[0 for _ in range(n+2)] for _ in range(m+2)]\n",
    "        row2 = [[0 for _ in range(n+2)] for _ in range(m+2)]\n",
    "        col1 = [[0 for _ in range(n+2)] for _ in range(m+2)]\n",
    "        col2 = [[0 for _ in range(n+2)] for _ in range(m+2)]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if grid[i-1][j-1] == 'E':\n",
    "                    row1[i][j] = row1[i][j-1] + 1\n",
    "                    col1[i][j] = col1[i-1][j] + 1\n",
    "                elif grid[i-1][j-1] == '0':\n",
    "                    row1[i][j] = row1[i][j-1]\n",
    "                    col1[i][j] = col1[i-1][j]\n",
    "        for i in range(m, 0, -1):\n",
    "            for j in range(n, 0, -1):\n",
    "                if grid[i-1][j-1] == 'E':\n",
    "                    row2[i][j] = row2[i][j+1] + 1\n",
    "                    col2[i][j] = col2[i+1][j] + 1\n",
    "                elif grid[i-1][j-1] == '0':\n",
    "                    row2[i][j] = row2[i][j+1]\n",
    "                    col2[i][j] = col2[i+1][j]\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if grid[i-1][j-1] == '0':\n",
    "                    res = max(res, row1[i][j-1]+row2[i][j+1]+col1[i-1][j]+col2[i+1][j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        dp1 = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        dp2 = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        dp3 = [[0 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        print(dp)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"W\":\n",
    "                    dp[i][j] = 0\n",
    "                    dp1[i][j] = 0\n",
    "                elif grid[i][j] == \"E\":\n",
    "                    x, y = 0, 0\n",
    "                    if i - 1 >= 0:\n",
    "                        x = dp[i - 1][j]\n",
    "                    if j - 1 >= 0:\n",
    "                        y = dp1[i][j - 1]\n",
    "                    dp[i][j] = x + 1\n",
    "                    dp1[i][j] = y + 1\n",
    "                else:\n",
    "                    x, y = 0, 0\n",
    "                    if i - 1 >= 0:\n",
    "                        x = dp[i - 1][j]\n",
    "                    if j - 1 >= 0:\n",
    "                        y = dp1[i][j - 1]\n",
    "                    dp[i][j] = x\n",
    "                    dp1[i][j] = y\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if grid[i][j] == \"W\":\n",
    "                    dp2[i][j] = 0\n",
    "                    dp3[i][j] = 0\n",
    "                elif grid[i][j] == \"E\":\n",
    "                    x, y = 0, 0\n",
    "                    if i + 1 < m:\n",
    "                        x = dp2[i + 1][j]\n",
    "                    if j + 1 < n:\n",
    "                        y = dp3[i][j + 1]\n",
    "                    dp2[i][j] = x + 1\n",
    "                    dp3[i][j] = y + 1\n",
    "                else:\n",
    "                    x, y = 0, 0\n",
    "                    if i + 1 < m:\n",
    "                        x = dp2[i + 1][j]\n",
    "                    if j + 1 < n:\n",
    "                        y = dp3[i][j + 1]\n",
    "                    dp2[i][j] = x\n",
    "                    dp3[i][j] = y\n",
    "\n",
    "        ret = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"0\":\n",
    "                    a, b, c, d = 0, 0, 0, 0\n",
    "                    if i - 1 >= 0:\n",
    "                        a = dp[i - 1][j]\n",
    "                    if i + 1 < m:\n",
    "                        b = dp2[i + 1][j]\n",
    "                    if j - 1 >= 0:\n",
    "                        c = dp1[i][j - 1]\n",
    "                    if j + 1 < n:\n",
    "                        d = dp3[i][j + 1]\n",
    "                    ans = a + b + c + d\n",
    "                    ret = max(ret, ans)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        ret=0\n",
    "        dp=[[[None,None] for _ in range(n)] for _ in range(m)]#[0]:up,down [1]:left,right\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]=='0' or grid[i][j]=='E':\n",
    "                    temp=0\n",
    "                    if j!=0 and dp[i][j-1][1]!=None:\n",
    "                        temp+=dp[i][j-1][1]\n",
    "                        dp[i][j][1]=dp[i][j-1][1]\n",
    "                    else:\n",
    "                        row_e=0\n",
    "                        for k in range(j,n):\n",
    "                            if grid[i][k]=='W':\n",
    "                                break\n",
    "                            elif grid[i][k]=='E':\n",
    "                                row_e+=1\n",
    "                        dp[i][j][1]=row_e\n",
    "                        temp+=row_e\n",
    "                    if i!=0 and dp[i-1][j][0]!=None:\n",
    "                        temp+=dp[i-1][j][0]\n",
    "                        dp[i][j][0]=dp[i-1][j][0]\n",
    "                    else:\n",
    "                        col_e=0\n",
    "                        for k in range(i,m):\n",
    "                            if grid[k][j]=='W':\n",
    "                                break\n",
    "                            elif grid[k][j]=='E':\n",
    "                                col_e+=1\n",
    "                        dp[i][j][0]=col_e\n",
    "                        temp+=col_e\n",
    "                    if grid[i][j]=='0':\n",
    "                        ret=max(ret,temp)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        ret=0\n",
    "        dp=[[[None,None] for _ in range(n)] for _ in range(m)]#[0]:up,down [1]:left,right\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]=='0' or grid[i][j]=='E':\n",
    "                    temp=0\n",
    "                    if j!=0 and dp[i][j-1][1]!=None:\n",
    "                        temp+=dp[i][j-1][1]\n",
    "                        dp[i][j][1]=dp[i][j-1][1]\n",
    "                    else:\n",
    "                        row_e=0\n",
    "                        for k in range(j,n):\n",
    "                            if grid[i][k]=='W':\n",
    "                                break\n",
    "                            elif grid[i][k]=='E':\n",
    "                                row_e+=1\n",
    "                        dp[i][j][1]=row_e\n",
    "                        temp+=row_e\n",
    "                    if i!=0 and dp[i-1][j][0]!=None:\n",
    "                        temp+=dp[i-1][j][0]\n",
    "                        dp[i][j][0]=dp[i-1][j][0]\n",
    "                    else:\n",
    "                        col_e=0\n",
    "                        for k in range(i,m):\n",
    "                            if grid[k][j]=='W':\n",
    "                                break\n",
    "                            elif grid[k][j]=='E':\n",
    "                                col_e+=1\n",
    "                        dp[i][j][0]=col_e\n",
    "                        temp+=col_e\n",
    "                    if grid[i][j]=='0':\n",
    "                        ret=max(ret,temp)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 给你一个大小为 m x n 的矩阵 grid ，其中每个单元格都放置有一个字符：\n",
    "\n",
    "# 'W' 表示一堵墙\n",
    "# 'E' 表示一个敌人\n",
    "# '0'（数字 0）表示一个空位\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, g: List[List[str]]) -> int:\n",
    "        m = len(g)\n",
    "        n = len(g[0])\n",
    "        def f(x):\n",
    "            n = len(x)\n",
    "            dic = {}\n",
    "            pre = {-1:0}\n",
    "            for j in range(n):\n",
    "                if x[j]=='E':\n",
    "                    pre[j] = pre[j-1] + 1 \n",
    "                else:\n",
    "                    pre[j] = pre[j-1]\n",
    "            st = -1 \n",
    "            a = {}\n",
    "            for j in range(n):\n",
    "                if x[j] == '0':\n",
    "                    a[j] = st \n",
    "                elif x[j] == 'W':\n",
    "                    st = j \n",
    "                        \n",
    "            b = {}\n",
    "            st = n\n",
    "            for j in range(n)[::-1]:\n",
    "                if x[j] == '0':\n",
    "                    b[j] = st \n",
    "                elif x[j] == 'W':\n",
    "                    st = j \n",
    "            c = {}\n",
    "            for j in range(n):\n",
    "                if x[j]=='0':\n",
    "                    c[j] = pre[b[j] - 1] - pre[a[j]] \n",
    "            return c\n",
    "        ans = 0\n",
    "        row = defaultdict(int)\n",
    "        for i in range(m):\n",
    "            t = f(g[i])\n",
    "            for j in t:\n",
    "                row[(i, j)] = t[j] \n",
    "        col = defaultdict(int) \n",
    "        for j in range(n):\n",
    "            t = f([g[i][j] for i in range(m)]) \n",
    "            for i in t:\n",
    "                col[(i, j)] = t[i] \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = max(ans, row[(i, j)] + col[i, j]) \n",
    "        return ans \n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        @functools.cache\n",
    "        def row(i,j,d):\n",
    "            total = 0\n",
    "            if grid[i][j] == \"E\":\n",
    "                total += 1\n",
    "            if j+d >=0 and j+d < n and grid[i][j+d]!=\"W\":\n",
    "                total += row(i,j+d,d)\n",
    "            return total \n",
    "\n",
    "        @functools.cache\n",
    "        def col(i,j,d):\n",
    "            total = 0\n",
    "            if grid[i][j] == \"E\":\n",
    "                total += 1\n",
    "            if i+d >= 0 and i+d < m and grid[i+d][j]!=\"W\":\n",
    "                total += col(i+d,j,d)\n",
    "            return total\n",
    "            \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"0\":\n",
    "                    res = max(res,row(i,j,1)+col(i,j,1)+row(i,j,-1)+col(i,j,-1))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        @functools.cache\n",
    "        def row(i,j,d):\n",
    "            total = 0\n",
    "            if grid[i][j] == \"E\":\n",
    "                total += 1\n",
    "            if j+d >=0 and j+d < n and grid[i][j+d]!=\"W\":\n",
    "                total += row(i,j+d,d)\n",
    "            return total \n",
    "\n",
    "        @functools.cache\n",
    "        def col(i,j,d):\n",
    "            total = 0\n",
    "            if grid[i][j] == \"E\":\n",
    "                total += 1\n",
    "            if i+d >= 0 and i+d < m and grid[i+d][j]!=\"W\":\n",
    "                total += col(i+d,j,d)\n",
    "            return total\n",
    "            \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"0\":\n",
    "                    res = max(res,row(i,j,1)+col(i,j,1)+row(i,j,-1)+col(i,j,-1))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKilledEnemies(self, grid: List[List[str]]) -> int:\n",
    "        #m,n = len(grid),len(grid[0])\n",
    "        #dirs = [[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        #@cache\n",
    "        #def back(x,y,bo):#0s,1x,2z,3y\n",
    "            #if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] == 'W':return 0\n",
    "            #return (grid[x][y] == 'E')+back(dirs[bo][0]+x,dirs[bo][1]+y,bo)\n",
    "        #return max([sum(back(i,j,x) for x in range(4)) for i in range(m) for j in range(n) if grid[i][j] == '0']+[0])\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        @functools.cache\n",
    "        def row(i,j,d):\n",
    "            total = 0\n",
    "            if grid[i][j] == \"E\":\n",
    "                total += 1\n",
    "            if j+d >=0 and j+d < n and grid[i][j+d]!=\"W\":\n",
    "                total += row(i,j+d,d)\n",
    "            return total \n",
    "\n",
    "        @functools.cache\n",
    "        def col(i,j,d):\n",
    "            total = 0\n",
    "            if grid[i][j] == \"E\":\n",
    "                total += 1\n",
    "            if i+d >= 0 and i+d < m and grid[i+d][j]!=\"W\":\n",
    "                total += col(i+d,j,d)\n",
    "            return total\n",
    "            \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"0\":\n",
    "                    res = max(res,row(i,j,1)+col(i,j,1)+row(i,j,-1)+col(i,j,-1))\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
